package com.yun.datastructure.graph;

import com.yun.datastructure.graph.domain.Edge;
import com.yun.datastructure.graph.domain.Vertex;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 利用动态规划处理负权重的边
 */
public class FloydWarshall {

    private static void floydWarshall(List<Vertex> graph) {
        int size = graph.size();
        int[][] dist = new int[size][size];
        Vertex[][] prev=new Vertex[size][size];
        //1.初始化
        for (int i = 0; i < size; i++) {
            Vertex v = graph.get(i);
            Map<Vertex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weight));
            for (int j = 0; j < size; j++) {
                Vertex u = graph.get(j);
                if (v == u) {
                    dist[i][j]=0;
                }else {
                    dist[i][j]=map.getOrDefault(u,Integer.MAX_VALUE);
                    prev[i][j]=map.get(u) != null?v:null;
                }
            }
        }
        print(prev);
        //2.看能否借路到达其他顶点
        /*
            v2->v1
            dist[1][0]
         */
        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    //dist[i][k]+dist[k][j]//i行的顶点，借助k顶点，到达j列顶点
                    if(dist[i][k]!=Integer.MAX_VALUE&&
                            dist[k][j]!=Integer.MAX_VALUE&&
                            dist[i][k]+dist[k][j]<dist[i][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];
                        if(dist[i][j]<0){
                            throw new RuntimeException("出现了负环");
                        }
                        prev[i][j]=prev[k][j];
                    }
                }
            }
            //print(dist);
        }
        print(prev);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                path(prev,graph,i,j);
            }
        }
    }

    static void print(int[][] dist) {
        System.out.println("----------");
        for (int[] row : dist) {
            System.out.println(Arrays.stream(row).boxed()
                    .map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }

    static void print(Vertex[][] prev){
        System.out.println("----------");
        for (Vertex[] row : prev) {
            System.out.println(Arrays.stream(row).map(v->v==null?"null":v.name)
                    .map(s->String.format("%5s",s))
                    .collect(Collectors.joining(",","[","]")));
        }
    }

    static void path(Vertex[][] prev,List<Vertex> graph,int i,int j){
        LinkedList<String> stack=new LinkedList<>();
        System.out.print("["+graph.get(i).name+","+graph.get(j).name+"] ");
        stack.push(graph.get(j).name);
        while (i!=j){
            Vertex p=prev[i][j];
            stack.push(p.name);
            j=graph.indexOf(p);
        }
        System.out.println(stack);
    }
}
